#include <bits/stdc++.h>
using namespace std;

/*
1277. 统计全为 1 的正方形子矩阵
已解答
中等
相关标签
premium lock icon
相关企业
提示
给你一个 m * n 的矩阵，矩阵中的元素不是 0 就是 1，请你统计并返回其中完全由 1 组成的 正方形 子矩阵的个数。

 

示例 1：

输入：matrix =
[
  [0,1,1,1],
  [1,1,1,1],
  [0,1,1,1]
]
输出：15
解释： 
边长为 1 的正方形有 10 个。
边长为 2 的正方形有 4 个。
边长为 3 的正方形有 1 个。
正方形的总数 = 10 + 4 + 1 = 15.
示例 2：

输入：matrix = 
[
  [1,0,1],
  [1,1,0],
  [1,1,0]
]
输出：7
解释：
边长为 1 的正方形有 6 个。 
边长为 2 的正方形有 1 个。
正方形的总数 = 6 + 1 = 7.
 

提示：

1 <= arr.length <= 300
1 <= arr[0].length <= 300
0 <= arr[i][j] <= 1
*/

// 法一
class Solution {
public:
    int countSquares(vector<vector<int>>& matrix) {
        // dp
        //  (i, j) 右下角最大正方形的边长
        // dp[i][j] 由上方 左方 左上方三个位置的dp来决定 
        // dp[i][j] = min([i - 1][j], [i][j - 1], [i - 1][j - 1] + 1)
        if (matrix.empty() || matrix[0].empty())    return 0;

        // 整个数组和首个dp位置的大小初始化
        int m = matrix.size();
        int n = matrix[0].size();
        vector<vector<int>> dp(m, vector<int>(n, 0));
        int ans = 0;

        // init 第一行
        for (int j = 0; j < n; j++) {
            dp[0][j] = matrix[0][j];
            ans += dp[0][j];
        }

        // init 第一列 从第二行开始避免重复'
        for (int i = 0; i < m; i++) {
            dp[i][0] = matrix[i][0];
            ans += dp[i][0];
        }

        // fill dp其他位置
        for (int i = 1; i < m; i++) {
            for (int j = 1; i < n; j++) {
                if (matrix[i][j] == 1)  dp[i][j] = min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]}) + 1;
                else    dp[i][j] = 0;

                ans += dp[i][j];
            }
        }
        return ans;
    }
};

// 法二 
// 常规暴力枚举 + 剪枝
class Solution {
public:
    int countSquares(vector<vector<int>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return 0;
        
        int m = matrix.size();
        int n = matrix[0].size();
        int max_len = min(m, n); // 正方形最大可能边长
        int count = 0;

        // 枚举所有左上角顶点 (i,j)
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                // 若当前顶点是 0，无法形成任何以它为左上角的正方形，直接跳过
                if (matrix[i][j] == 0) continue;
                
                // 枚举可能的边长 k（从 1 开始，直到最大合法边长）
                // 最大合法边长：确保右下角 (i+k-1, j+k-1) 不越界
                int max_k = max_len;
                if (i + max_k > m) max_k = m - i;
                if (j + max_k > n) max_k = n - j;
                
                // 检查边长为 1 到 max_k 的正方形
                for (int k = 1; k <= max_k; ++k) {
                    bool is_valid = true;
                    // 检查正方形的「最外层右边和下边」（剪枝优化：内层已在小边长时检查过）
                    for (int x = i; x < i + k; ++x) {
                        if (matrix[x][j + k - 1] == 0) {
                            is_valid = false;
                            break;
                        }
                    }
                    if (!is_valid) break;
                    
                    for (int y = j; y < j + k - 1; ++y) {
                        if (matrix[i + k - 1][y] == 0) {
                            is_valid = false;
                            break;
                        }
                    }
                    if (is_valid) {
                        count++;
                    } else {
                        // 边长 k 不合法，更大的 k 也必然不合法，直接终止
                        break;
                    }
                }
            }
        }
        return count;
    }
};


// 法三
// dp 优化 升维 不用额外判断越界情况
class Solution {
public:
    int countSquares(vector<vector<int>>& matrix) {
        int ans = 0;  // 用于累计所有全1正方形子矩阵的数量
        int n = matrix.size(), m = matrix[0].size();  // n是矩阵行数，m是矩阵列数
        
        // 定义dp数组f，维度为(n+1)×(m+1)，初始值全为0
        // 这样定义是为了简化边界处理：当i=0或j=0时，不需要额外判断越界
        // f[i+1][j+1] 表示以原矩阵中(i,j)为右下角的最大正方形边长
        vector f(n + 1, vector<int>(m + 1));
        
        // 遍历原矩阵的每个元素(i,j)
        for (int i = 0; i < n; i++){
            for(int j = 0; j < m; j++) {
                // 只有当当前位置是1时，才可能形成正方形
                if(matrix[i][j]) {
                    // 递推公式：当前位置的最大正方形边长 = 左、上、左上三个方向的最小边长 + 1
                    // 因为f是(n+1)×(m+1)维度，所以：
                    // f[i][j] 对应原矩阵(i-1,j-1)的左上位置
                    // f[i][j+1] 对应原矩阵(i-1,j)的上方位置
                    // f[i+1][j] 对应原矩阵(i,j-1)的左方位置
                    f[i + 1][j + 1] = min({f[i][j], f[i][j + 1], f[i + 1][j]}) + 1;
                    
                    // 累加当前位置贡献的正方形数量：边长为1到f[i+1][j+1]的正方形各1个，总和就是f[i+1][j+1]
                    ans += f[i + 1][j + 1];
                }
                // 若当前位置是0，则无法形成任何正方形，f[i+1][j+1]保持初始0，不影响结果
            }
        }
        return ans;
    }
};